//给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 
//
// 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 
//
// 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 
//
// 
//
// 示例 1： 
//
// 
//输入：x = 4
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：x = 8
//输出：2
//解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
// 
//
// 
//
// 提示： 
//
// 
// 0 <= x <= 231 - 1 
// 
// Related Topics 数学 二分查找 
// 👍 826 👎 0

package com.cute.leetcode.editor.cn;
public class Sqrtx {
    public static void main(String[] args) {
        new Sqrtx().new Solution().mySqrt(2147395599);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 1.使用二分法来寻找一个值而已，一开始的右区间就定到x/2
         *      使用乘法的时候注意数据溢出
         * 2.也可以使用牛顿法
         *      随便猜一个>0的数a认为是方程的根，每次只需要逼近就可以了
         *      long x = a;
         *      while (x * x > a) x = (x + a / x) / 2;
         *      return (int)x;
         *
         */
        public int mySqrt(int x) {
            if (x <= 1 ) return x;
            int left = 1;
            int right = x / 2;
            int mid;
            while (left <= right){
                /**
                 * 当left==right的时候进入循环
                 * 如果mid**2>x，此时right会减一，right是离结果最近的一个
                 * 如果mid**2<x，此时left会+1，left+1后会比right大，且left+1**2绝对会比x大，所以right还是最近接结果的那一个
                 * 所以循环退出之后返回right就可以或者返回left-1
                 */
                mid = left + (right - left)/2;
                if (mid > x / mid){
                    right = mid -1;
                }else if (mid < x / mid){
                    left = mid +1;
                }else return mid;
            }
            return right;
        }

        // 二刷的时候的写法
        public int mySqrt2(int x) {
            // 找到第一个平方 <= x的数
            if (x <= 1) return x;
            // 这样表示r也可能是结果
            int l = 1, r = x / 2, mid;
            while (l < r){
                // mid向上取整防止死循环，判断条件更简单一些，不向上取整时比较麻烦
                mid = l + (r - l + 1) / 2;
                if (mid > x /mid) r = mid - 1;
                else l = mid;
            }
            return l;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}